COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP
C00004 00003	REVIEW OF AM
C00034 00004	PROBLEMS WE FACE
C00044 00005
C00047 ENDMK
C⊗;
.DEVICE XGP

.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "BDR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT A "SUP"
.FONT B "SUB"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.PAGE FRAME 54 HIGH 80 WIDE
.AREA TEXT LINES 4 TO 53
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER←EVENLEFTBORDER←1000
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO B1 ⊂ BEGIN PREFACE 0 INDENT 0 SINGLE SPACE ⊃
.MACRO E ⊂ APART END ⊃
.MACRO FAD ⊂ FILL ADJUST DOUBLE SPACE PREFACE 2 ⊃
.MACRO FAS ⊂ FILL ADJUST SINGLE SPACE PREFACE 1 ⊃
.FAS
.PAGE←0
.NEXT PAGE
.INDENT 0
.TURN OFF "{∞→}"   
.GROUP SKIP 1
.BEGIN CENTER  PREFACE 0

⊗5↓_AUTOMATED   MATHEMATICIAN_↓⊗*

⊗5↓_ADVANCED  TALK_↓⊗*


for the Stanford ⊗2Heuristic Programming Project⊗* Workshop

⊗4January 5-8, 1976⊗*


Douglas B. Lenat



.END
.SELECT 1
.EVERY HEADING(⊗7Douglas B. Lenat⊗*,⊗4↓_Automated Mathematician_↓⊗*,⊗7ADVANCED Seminar      page   {PAGE}⊗*)

REVIEW OF AM

Let me open with a 10-minute review of the AM project. After that, I'll talk
a little about some issues in my research that bear on theory formation
or heuristic programming in general, and we can all discuss them.

The objective of this project is to emulate a mathematician doing simple
research. 
The reasons are to study the theory formation process in empiricial science.

As I mentioned Monday,
⊗5Math was chosen⊗* as the science to work in partly because I wouln't have to
deal with nonprogramming experts in a domain alien to me; I could collect my
heuristics by introspection. But that's not
the main suitability for math research as a
task domain for an AI theory formation program. It is that of all scientists, the
mathematician is the least encumbered by reality, by the need to solve a specific
problem. Instead of being driven by practical problems, the mathematician is
↓_driven by his intuition_↓, his aeshtetic sense, his appreciation of the
unusual. He looks at something because he thinks it might prove interesting,
and he publishes something because he thinks it did prove interesting.

I believe that ↓_math is an empirical science_↓, and that it is possible to
write down precise heuristics about the 
notion of aesthetic interestingness, about what is a promising new concept
to define and study, what new aspect to consider, about when to quit and move on.
A typical one of these hints is to look for situations where you might
complete a square of functions. ⊗5<square slide>⊗* This particular case occurs
when you know about  bags, cross-product, and counting the length of a bag.
The missing operation here can be calculated, and in fact defined, using
just these three known operations to define it. It turns out to be what
you and I call multiplication.

One reason for AM to exist as a program is to see if these heursitics are
really powerful enough to push the system along fruitful lines of development.
⊗5<tree of concepts slide>⊗* The heuristic of completing the square can take
you from here to here, for example. THe heuristic of investigating the
inverse of each new, interesting relation, will take you from here to here
and also along this path, to the discovery of divisors. The heuristic of
looking for elements which give extreme results will lead you from divisors
to considering numbers with unusual numbers of divisors. Two extremes are
what we call primes, and a class of numbers which has no name as of yet.
Primes are characterized by saying that a number is in here if its only divisors
are itself and 1.
Numbers in ⊗4this⊗* class have many divisors, and can be characterized by
saying that a number is in here if it has more divisors than every smaller
natural number. Another way to look at it is, we put in here the smallest
natural number with 2 divisors, the smallest number with 3 divisors, 
the smallest number which has 8 million divisors, etc.

But why has ⊗2↓_everybody heard of these_↓⊗*, and nobody heard of these?
Well, the reason is that there are many theorems about primes, many
proofs in number theory that use primes, a canonical reeresentation
of numbers decomposed into prime factors, and so on. Why is ⊗4this⊗* unheard of?
Because until last weekend, there were no theorems about this set of numbers,
no proofs that would go easier if you used them somehow, no ties to any other
known concepts, except in the way they were defined. Last weekend, based on
suggestions from AM, Randy and I established a meaningful conjecture about
this concept. I think we have a method for generating an infinite sequence
of numbers of this type. In particular, they all have the following form
⊗5<Max slide>⊗*. I won't force you through this again today.

At each moment, a mathematician, just like  AM, has a
list of hundreds of concepts 
which he knows something about. His basic activity is to
find out more about those concepts, and in so doing he occasionally
decides that some new concept is worth naming and investigating.

In the AM program, each concept can have many different kinds of
knowledge tacked onto it ⊗5<facets slide>.⊗*
Some of this is actually a collection of heuristics, 
written as productions,
which contain hints for dealing with the concept: why it is useful, how one
of these might be interesting, how to fill in more knowledge about of one of these,
suggestions for new activities to try (some relating to this concept,
some to others), and warnings of traps not to fall into when
handling this concept.⊗2<slide for COMPOSE concept>⊗*
Here is a typical concept.
Note that I've indicated that the system maintains multiple representations for
the same knowledge. We may talk about that later.

WHAT does the system actually do, then? It expands its knowledge, 
both by
creating new concepts and by finding out more about the already-known ones.
That means it creates new data structures like these, and it fills out
the facets of existing ones.

The basic control structure can be characterized as
⊗5<planning slide>⊗*
a select, plan, and execute loop.
The selection is made from a global list of things AM thinks are worth
doing. Each of these has tacked onto it a predicate indicating why
it was suggested, how to quantitatively estimate its worth, and so on.
So selecting is done by asking each of these how promising it is
at the moment.

The statement of the activity to be performed is itself a simple kind of
plan. 
That is, these are all really plans for things that AM might do.
It isn't of the form "Compose Set-intersect with Complement", but
rather just "Do ⊗4some⊗* composition". 

At this stage, a plan of attack
is assembled by throwing together all the heuristics who have anything to say
about  either this activity or one of these operands.
Recall that heuristics are represented as productions.
By running the resultant production system, this task should get done.

During this execution, several things may happen. 
Depending on the outcome, some of the relevant heuristics might make
↓_new suggestions_↓ on what would be interesting to do.
Here, if no examples were found, one heuristic might suggest
that AM sometime consider generalizing the concept of Compose.
Sometimes, some ↓_new concepts will be created_↓. Any interesting examples
of Compose which are found will be operations themselves, hence
can be considered as potential concepts.

For those facets which are stored as procedures, filling them in will mean writing
new little programs. Well, we know enough about automatic programming to
do that. 
This is the kind of task that I worked on with Cordell for 2 years.
The knowledge tacked onto  the 
Fillin facet of the
Algorithms concept, for example,
will be automatic programming techniques, which can use, say, the definition
of any concept to produce an executable algorithm for it.
In fact, the representation used for concpets 
is not simply the property list one, but
rather the BEINGs one, which was developed for automatic programming.
I intentionally want to ignore that aspect of AM, since I don't think it has
any relevance to theory formation in general.
Instead, let's discuss some of the more general questions that AM raises.
PROBLEMS WE FACE

Updating Knowledge Base:

One  problem we all face is how to cope with changes in the system's knowledge
base. The standard solution is to track down all the effects of each change, and
update the whole data base. The solution AM uses, and perhaps people too, is to
just record the changed information, and ⊗4not⊗* to update everything.
When a contradiction of some kind occurs, then the conflicting knowledge
is checked, the knowledge ⊗4it⊗* was based on is checked, 
and so on, until we encounter
some changed opinion which explains the disagreement.
So the system is allowed to hold contradictory
viewpoints, so long as it could resolve any dispute if it had to.
This is one solution you might keep in mind for your knowledge-based systems.

How to measure performance

There is no specific "goal" that AM is supposed to achieve; in fact, the 
specification of any such preconceived goal would probably interfere with
creating a system general enough to explore a large space of concepts.
We could set some milestones out, like
Define some brand new concept; making a new conjecture; finding 
some new result which is not only interesting but useful.
Developing an entirely new theory.
A crude approximation  to this might be where its results were
publishable. In journals in AI? in the chosen scientific field?
in Scientific American?
Or we could construct some more relative criteria to judge its performance by
Comparing the given initial knowledge to the derived knowledge.
Examining the route AM took to do anything, its chains of reasoning and guessing.
You could rate a theory formation system as a user program: can researchers
in its field actually use it effectively. Does it do what ⊗4they⊗* would
like it to? Is the program a good enough theorist that it becomes worthwhile
to perform experiments with it (removing, adding, modifying the heuristics and
the starting concepts, and seeing the results).


Role of the user
Continuum from passive observor, to active co-researcher, to absolute
mentor (latter ex: the FOL Proof-checker).
What is the optimum role? Assume it changes dynamically. Is there any
general criteria we can cite for when you do/don't want the user to
say something? The more he must do, the better informed he must be about
what the system is doing, why, and how. 



What considerations come into play when choosing a name for the system,
There is the danger of being pretentious:
HACKER, PLANNER, CONNIVER, A.M.,LOGIC THEORIST, GPS.
Or the strange other extreme, of intentional meaninglessness:
GOOOOO37.

Affect of data structure reprs. and other hidden assumptions in a theory formation
pgm that limit its potential. EG: meta-dendral: limited to inferring a
grammar whose rules have a certain kind of format. The way AM is set up, t is
more natural for it to derive our concepts of number than Knuth's surreal ones.

Intuition: its role in math research (guide, check), AM (abstract manip. reprs).
Is it the same as that of abstraction spaces? Hence, same as planning?

Acquiring new Heurisitcs is considerably harder than the previous paradigm of
theory formation. It requires a quantum leap of insight and daring, and
much longer periods of time to test it out. The heuristics for acquiring
new heuristics are almost unthinkable. Newell's suggestion: go through the
development of math (or any sim. sci), and factor out all the hack discoveries
-- the kind that AM might be able to make. What you have left would basically
be a sequence of these huge leaps, where either luck or some piece of this
heuristic-generating knowlege created a new heuristic which led to a new
kind of discovery. An example is Einsten's doubting the common-sense
notions of simultaneity, or Riemann denying Euclid's parallel postulate.
After the first move of this kind, 
the first time someone considered denying what was hitherto unquestioned,
what was so intuitively true that it had never occurred to anyone that
denying it could lead to consistent results.
It became a standard heuristic which
physicists and mathematicians now use quite frequently.

What it would take to be able to do research in various areas of mathematics,
in other sciences, in softer fields like sociology (the concept of CLAN, POWER).
The possibility that you might be able to represent concepts, albeit crudely,
but good enuf to get some interesting results (e.g., prediction of new psychological
effects, or at least interesting experiments to try, even  though the facets
of the concept labbelled HUMANS will not be complete).

Justification for starting knowledge and heuristics
Minimal, complete, analogous to some human/group of humans (children:Piaget).

Overestimation of our own understanding of phenomena
Because when you talk to yourself or another human, you needn't be as precise
as when talking to a PDP10.

What characteristics make a task ripe for attack by AI methods, say heuristic
programming methods.
The experts in the field are much better than the average intelligent man.
E.g.: chess, math, Mycin's Task, ...
OR: The combinatorial nature of the problem is between one and four orders of magnitude
above human abilities. EG: CONGEN.
OR: The task is thought to be intellectual by the scientific community, whether
it is or not (preparing detailed astrological charts may be very complex, but
no one here would respect a program very much that did that. Many management
sciences algorithms are kept from being considered part of AI because of the
nonscientific motivations and uses they're put to).

.GROUP

Plans for the future

.B1 GROUP

intuitions

expanded breadth -- new domains of math, of science (chem. concepts: an O=C-C-¬C)

expanded depth -- deeper no. thy. results, new rsults

better user interface

experiments

documentation, public relations, papers, talks

theoretical analysis, extracting the new key ideas and cleaning them off.

AM next year at SStanford? anywhere? more diss. topics?

.E